package Array;

import java.util.*;

public class item239 {
    public static int[] maxSlidingWindow(int[] nums, int k) {
//超时了
        if(nums == null || nums.length < 2) return nums;
        // 双向队列 保存当前窗口最大值的数组位置 保证队列中数组位置的数值按从大到小排序
        int []res = new int[nums.length-k+1];
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < nums.length ; i++) {
            if (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]){
                queue.pollLast();
            }
            queue.addLast(i);
            if(queue.peek()<=i-k)
            {
                queue.poll();
            }
            if(i+1-k>=0)
            {
                res[i+1-k]=nums[queue.peek()];
            }

        }
       return res;

    }

    public static void main(String[] args) {
        int []nums ={1,3,-1,-3,5,3,6,7};
        maxSlidingWindow(nums,3);
    }



}
